import java.util.*;

/**
 * 20. 有效的括号
 * <p>
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * <p>
 * 示例 1：
 * 输入：s = "()"
 * 输出：true
 * 示例2：
 * 输入：s = "()[]{}"
 * 输出：true
 * 示例3：
 * 输入：s = "(]"
 * 输出：false
 */
public class isValid {
    public static void main(String[] args) {
        System.out.println(isValid_2("(()[{()}]{})"));
        System.out.println("++++++++++++++++++++");
        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        stack.push("{".charAt(0));
        stack.push("3".charAt(0));
        stack.pop();
        System.out.println(stack.peek());


    }

    /**
     * 自己的解决方案
     * <p>
     * 2 ms(53.74%)	41.1 MB(7.66%)
     *
     * @param s
     * @return
     */
    public static Boolean isValid_1(String s) {
        if (s == null || s.length() <= 1 || s.length() % 2 != 0) return false;
        List<String> cache = new ArrayList<>();
        cache.add(getValid(s.charAt(0) + ""));
        for (int i = 1; i < s.length(); i++) {
            int LastIndex = cache.size() - 1;
            if (LastIndex != -1 && cache.get(LastIndex).equals(s.charAt(i) + "")) {
                cache.remove(LastIndex);
            } else {
                cache.add(getValid(s.charAt(i) + ""));
            }
        }
        return cache.size() <= 0;
    }

    /**
     * 获取有效的互补括号
     * ()[]{}
     *
     * @param s
     * @return
     */
    public static String getValid(String s) {
        String valid = "";
        if (s.equals("(")) {
            valid = ")";
        } else if (s.equals("[")) {
            valid = "]";
        } else if (s.equals("{")) {
            valid = "}";
        }
        return valid;
    }

    /**
     * 2 ms(53.74%)	39.6 MB(26.04%)
     *
     * @param s
     * @return
     */
    public static Boolean isValid_2(String s) {
        int n = s.length();
        if (n % 2 == 1) return false;

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }


    /**
     * 逆序字符串
     *
     * @param originStr
     * @return
     */
    public static String reverse(String originStr) {
        if (originStr == null || originStr.length() <= 1) return originStr;
        return reverse(originStr.substring(1)) + originStr.charAt(0);
    }

}
